package com.mango.leet.code.easy;
/**
 * 14. 最长公共前缀
 */
/**
 * 编写一个函数来查找字符串数组中的最长公共前缀。
 *
 * 如果不存在公共前缀，返回空字符串 ""。
 *
 *  
 *
 * 示例 1：
 *
 * 输入：strs = ["flower","flow","flight"]
 * 输出："fl"
 * 示例 2：
 *
 * 输入：strs = ["dog","racecar","car"]
 * 输出：""
 * 解释：输入不存在公共前缀。
 *  
 *
 * 提示：
 *
 * 1 <= strs.length <= 200
 * 0 <= strs[i].length <= 200
 * strs[i] 仅由小写英文字母组成
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/longest-common-prefix
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

/**
 * @Author: mango
 * @Date: 2022/3/19 11:20 下午
 */
public class LC14_LongestCommonPrefix {
    public static void main(String[] args) {
        //String[] strs = {"flower","flow","flight"};
        String[] strs = {"dog","racecar","car"};
        System.out.println(new Solution().longestCommonPrefix(strs));
    }
    static class Solution {
        // 分治
        public String longestCommonPrefix(String[] strs) {
            return getPrefix(strs,0,strs.length-1);
        }

        private String commonPrefix(String leftPrefix, String rightPrefix) {
            int len = leftPrefix.length() < rightPrefix.length() ? leftPrefix.length() : rightPrefix.length();
            for(int i=0;i<len;i++){
                if(leftPrefix.charAt(i) != rightPrefix.charAt(i)){
                    return leftPrefix.substring(0,i);
                }
            }
            return leftPrefix.substring(0,len);
        }

        public String getPrefix(String[] strs,int left,int right){
            if(left == right){
                return strs[left];
            }
            int mid = (left + right) / 2;
            String leftPrefix = getPrefix(strs,left,mid);
            String rightPrefix = getPrefix(strs,mid+1,right);
            return commonPrefix(leftPrefix,rightPrefix);
        }
        // 纵向扫描
        public String longestCommonPrefix2(String[] strs) {
            int i=0;
            String prefix = "";
            Character temp = null;
            boolean find = true;
            while (find) {
                for (int m = 0; m < strs.length; m++) {
                    if (strs[m].length() <= i) {
                        find = false;
                        break;
                    }
                    if (temp == null) {
                        temp = strs[m].charAt(i);
                    }
                    if(!temp.equals(new Character(strs[m].charAt(i)))){
                        find = false;
                        break;
                    }
                    if(m == strs.length-1){
                        prefix += temp;
                        temp = null;
                    }
                }
                i++;
            }
            return prefix;
        }
    }
}
